class Solution(object):
    def maximumGap(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) == 1:
            return 0
        min_value = nums[0]
        max_value = nums[0]
        length = len(nums)
        for i in range(1, length):
            min_value = min(min_value, nums[i])
            max_value = max(max_value, nums[i])
        dist = max(1, (max_value - min_value) // length)
        budgets = [[] for _ in range((max_value - min_value) // dist + 1)]
        len_budgets = len(budgets)
        for item in nums:
            budgets[(item - min_value) // dist].append(item)
        left_index = 0
        right_index = 1
        max_dist_budget = 1
        max_left = set()
        while right_index < len_budgets:
            if not budgets[right_index]:
                right_index += 1
            else:
                if right_index - left_index > max_dist_budget:
                    max_dist_budget = right_index - left_index
                    max_left = {left_index}
                else:
                    if right_index - left_index == max_dist_budget:
                        max_left.add(left_index)
                left_index = right_index
                right_index += 1
        max_value = 0
        for item in max_left:
            min_item = max(budgets[item])
            max_item = min(budgets[item + max_dist_budget])
            max_value = max(max_value, max_item - min_item)
        return max_value


data = Solution()
nums = [2, 2, 4, 5, 7, 11]
print(data.maximumGap(nums))